/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-13
 * Time: 22:35
 */
public class Solution {
    // 动态规划
    // F(i, j) 表示 s1 的前 i 个字符转化为 s2 的前 j 个字符需要的最少的操作次数
    public int minDistance (String word1, String word2) {
        // write code here
        int row = word1.length();
        int col = word2.length();
        // minDist[i][j] 表示在 word1 的前 i 个字符转换为 word2 的前j 个字符的最小 次数
        int[][] minDist = new int[row + 1][col + 1];
        // 空字符串转化为一个字符串的最小操作次数就是一直插入
        for (int i = 0; i <= row; i++) {
            minDist[i][0] = i;
        }
        // 一个字符串转化为空字符串的最小操作次数就是一直删除
        for (int i = 0; i <= col ; i++) {
            minDist[0][i] = i;
        }
        for (int i = 1; i <= row ; i++) {
            for (int j = 1; j <= col ; j++) {
                // 插入 F(i, j) = (i, j - 1) + 1
                // 删除 F(i, j) = (i - 1, j) + 1
                minDist[i][j] = Math.min(minDist[i][j-1], minDist[i-1][j]) + 1;
                // 替换的话, 字符串的长度并不变化, 所以需要先判断用不用替换
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    // 说明不需要替换
                    minDist[i][j] = Math.min(minDist[i-1][j-1], minDist[i][j]);
                }else{
                    minDist[i][j] = Math.min(minDist[i-1][j-1] + 1, minDist[i][j]);
                }

            }
        }
        return minDist[row][col];
    }
}
